Set TSP problem
GENERALIZATION OF THE TRAVELING SALESMAN PROBLEM (TSP), WHEREBY IT IS REQUIRED TO FIND A SHORTEST TOUR IN A GRAPH WHICH VISITS ALL SPECIFIED SUBSETS OF THE VERTICES OF A GRAPH
Set TSP; Group TSP; Multiple Choice TSP; One-of-a-Set TSP; Covering Salesman Problem; GTSP; Generalized TSP
In combinatorial optimization, the set TSP, also known as the generalized TSP, group TSP, One-of-a-Set TSP, Multiple Choice TSP or Covering Salesman Problem, is a generalization of the traveling salesman problem (TSP), whereby it is required to find a shortest tour in a graph which visits all specified subsets of the vertices of a graph. The subsets of vertices must be disjoint, since the case of overlapping subsets can be reduced to the case of disjoint ones.